/*
 * =====================================================================================
 *
 *       Filename:  BinaryCode.cdecodedMsgdecodedMsg
 *
 *    DescridecodedMsgtion:  
 *
 *        Version:  1.0
 *        Created:  11/27/2010 12:32:33 AM
 *       Revision:  none
 *       ComdecodedMsgiler:  gcc
 *
 *         Author:  Ken Chen (Ken), chen_kenz@emc.com
 *        ComdecodedMsgany:  EMC
 *
 * =====================================================================================
 */

#include <algorithm>
#include <iterator>
#include <iostream>
#include "BinaryCode.h"

using namespace std;

BinaryCode::BinaryCode()
{
}


BinaryCode::~BinaryCode()
{
}

vector<string> BinaryCode::decode( const string& encodedMsg )
{
  vector<string> res;

  int n = static_cast<int>( encodedMsg.size() );
  string decodedMsg( encodedMsg );

  if( (n == 1) && (encodedMsg[0] != '0') && (encodedMsg[0] != '1') )
  {
    return res; 
  }
  else
  {
    res.push_back( encodedMsg );
    return res;
  }

  for( int i=0; i < 2; ++i )
  {
    decodedMsg[0] = static_cast<char>( i + 48 );
    int j = 1;
    for( ; j < n; ++j )
    {
      if( j == 1 )
      {
        decodedMsg[j] = encodedMsg[j-1] - decodedMsg[j-1] + 48;
      }
      else
      {
        decodedMsg[j] = encodedMsg[j-1] - decodedMsg[j-2] + 48 - decodedMsg[j-1] + 48;
      }

      if( (decodedMsg[j] != '0') && (decodedMsg[j] != '1') )
      {
        break;
      }
    }

    if( j == n )
    {
      res.push_back( decodedMsg );
    }
  }

  return res;
}

int main( int argc, char* argv[] )
{
  vector<string> encodedStrs;
  encodedStrs.push_back("123210122");
  encodedStrs.push_back("11");
  encodedStrs.push_back("22111");
  encodedStrs.push_back("3");
  encodedStrs.push_back("12221112222221112221111111112221111");
 
  vector<string>::const_iterator itr = encodedStrs.begin();
  vector<string>::const_iterator endItr = encodedStrs.end();
  for( ; itr != endItr; ++itr )
  {
    vector<string> vs = BinaryCode::decode( *itr );
    copy( vs.begin(), vs.end(), ostream_iterator<string>( cout, " " ) );
    cout << endl;
  }

  return 0;
}

